Mobile Ad-hoc NETworks (MANETs) are self-formed and self-healing wireless networks that support data and/or voice communication between mobile or stationary nodes without any physical infrastructure.
A MANET is a type of “Mesh Network”, with added mobility capabilities. In Mesh Networking, each node in the network may act as an independent router, regardless of whether or not it is connected to another network. It provides continuous connections and reconfiguration around broken or blocked paths by “hopping” from a node to another node, until the destination is reached. FIG. 1 (prior art) shows an exemplary connection path between node “A” and node “B” in a typical Mesh network.
Mesh networks are self-healing: the network can still operate when one node breaks down or when the quality of a connection is low. MANET is a mesh network, capable of dealing with the problems introduced by the mobility of the nodes. One of the drawbacks of Mesh networks is that if several subscribers need to hop through the same node, this creates a “bottleneck” at that node, and the data rate of the contending subscribers is substantially reduced.
Each mobile node manages dynamic routing tables that track the MANET topology. The routing tables may be established by running any routing protocol suitable for MANETs, for example Optimized Link State Routing protocol (OLSR—an IP routing protocol optimized for mobile ad-hoc networks) or Ad hoc On-Demand Distance Vector routing protocol (AODV—a routing protocol for mobile ad hoc networks). OLSR is a proactive Link State (LS) algorithm that holds the radio link status information, and AODV is a reactive Distance Vector (DV) algorithm that holds only the distances to all the other nodes. The topology may possibly include additional parameters, such as link quality, physical location and channel frequency.
MANETs can be used either in military environment, or in areas where the existing infrastructure collapsed (e.g., disaster areas) or is not sufficient. In the recent years, there has been a growing need for wideband MANET capabilities to support more users (nodes) and more demanding applications. However, the spectrum resource is scarce, and the current MANET algorithms do not exploit the spectrum efficiently enough, in order to meet the growing needs.
The MANET nodes are identified by a node ID and run a distributed Medium Access Control (MAC) algorithm that allocates time resources to nodes in every MANET channel. The system utilizes a limited number of radio channels, while managing every channel separately, and dividing the timeline of each channel between the MANET nodes. If the timeline is divided to slots (as shown in FIG. 2), the time division between MANET nodes is called “TDMA”, namely Time Division Multiple Access (a channel access method for shared medium networks that allows several users to share the same frequency channel by dividing the signal into different time slots).
In wireless MANET networks, sophisticated distributed algorithms are needed to manage the access to several radio channels, determining for every node when to receive and when to transmit in any channel, for each time period.
In a standard MANET setting (where the transceiver can receive only one channel at a time), once the channel frequency has been set, the mesh networking is carried on only among the subscribers that are tuned to that channel, and the MAC algorithm has meaning only within the selected channel, and is blind to all other channels. Although the channel frequency can be selected among many frequencies, once it has been chosen, it becomes unrelated to the networking operation. Thus, a MANET system with a collection of channels, is in fact a collection of unconnected parallel MANET systems, each one working on its own channel only, with data rate and reliability performance limited by the width of one single channel. This observation is also true when the timeline is divided in time slots: during every time slot, in every channel, a different MANET is managed, and the participants of that MANET run distributed algorithms to decide how to divide the channel between them (i.e., to determine which node will transmit at what time).
Several algorithms have been proposed for providing improved data throughput to conventional MANETs, by using an architecture that includes multi-channel full-duplex (capable of receiving during transmission) or half-duplex (not receiving during transmission) transceivers. However, these algorithms are topology-transparent, namely, do not consider how many nodes in the system are actually there (are actually “live”). Rather, all the potential nodes in the system are assigned a “frequency selection table” with different transmission frequencies for each node, according to a predetermined algorithm, such as a Latin Square (an n×n array filled with n different symbols, each occurring exactly once in each row and exactly once in each column), while all the individual patterns are predetermined, and designed so to avoid collisions when the system is “fully populated” (close to its maximum capacity) by live nodes. The hopping patterns are constructed mostly using mathematical tools such as “Orthogonal Latin Squares” (n×n arrays filled with n different Latin letters, each occurring exactly once in each row and exactly once in each column, so that when they overlap, all possible pairs of letters occur), which ultimately generate simultaneous transmit/receive frequency pairs which never collide within the same time slot. However, such a collision-avoiding frequency pattern planning is global in nature, and involves using the whole available spectrum at once (in full duplex mode), or a fixed number of frequencies (in half-duplex mode). Therefore, the frequency usage is non-adaptive, and a substantial spectral efficiency improvement can be achieved only if the number of active nodes is close to the maximal allowable number of nodes in the system. If the system is not fully populated, the spectral efficiency drops drastically.
Clearly, since one of the main requirements of ad-hoc systems is to function while the number of live nodes may change abruptly without notice, the topology-transparent approach cannot ensure a consistent efficiency improvement and scalability.
In topology-transparent systems, if the number of nodes is small compared to its maximal allowable limit, the “whole band” hopping sequence may be longer than needed. It follows that there are “dead times” while a node uselessly hops through non-populated channels. This results in unnecessary idle periods where a node is not available. Moreover, if a node must transmit some recurrent information, such as present location data, the time period between refresh transmissions may become unnecessarily long, and the system information accessibility is impaired.
Most algorithms proposed in the prior-art references, assume that the nodes are capable of full-duplex operation (simultaneous reception during transmission), and this assumption is crucial in achieving a fully-populated spectral efficiency improvement. Anyone skilled in the art, is aware that implementing a full-duplex transceiver requires substantial separation between the transmit band and the receive band. This is because the wideband phase noise “tail” generated at the receive frequency by the synthesizer of the transmitter, causes an extremely powerful “white noise” to enter the receiver input. The power of this noise is always much greater than the desired signal to be received, and, unless filtered out before reaching the receiver input, will cause strong receiver “desensitization”, namely, a dramatic loss of sensitivity, up to a total system crash. Therefore, when designing full-duplex transceivers, one must add a component known as a “duplexer”. A duplexer is in essence a set of filters that perform the (relatively easy) task of preventing the power at transmit frequency from burning out the receiver, and the (difficult) task of clearing up the transmitter noise tail at receiving frequency, so to prevent receiver desensitization. Usually, the power of the noise tail at receive frequency must be reduced by a factor of at least 50 dB (five orders of magnitude), which can be done only if the transmitting band is well separated from the receive band (at least several times the whole operational bandwidth), and even then, the duplexer turns out to be a bulky and costly unit. If the transmit and receive bands are close, or even worse, if they overlap or are interleaved, the construction of a full-duplex transceiver is not feasible. To make things worse, the required transmitter-tail to receiver-input isolation cannot be achieved in mobile equipment by using separate transmit and receive antennas, since this would require a physical vertical separation of several meters, which can be achieved only using fixed pole-top-mounted antennas. Therefore, in many actual scenarios, one cannot make use of the prior-art full-duplex algorithms mentioned before.
Another prior-art topology-transparent algorithm makes use of a half-duplex transceiver, while utilizing a fixed number of frequencies, which is about half the number of the nodes in a fully populated system. Such algorithm has a two-fold drawback: (a) it cannot reach the best spectral-efficiency and time-efficiency on a sparsely-populated system, because the number of frequencies cannot adapt itself when the number of nodes changes, (c) even if the number of available frequencies is much more than dictated by the number of “live” nodes, the algorithm cannot dynamically add frequencies, and therefore, cannot utilize the whole available band in order to improve the system immunity or the transmission range.
The fact that the algorithms proposed in the prior-art references are “Topology transparent” (i.e., are “blind” to the number of live nodes in the system, and to alien transmitters) limits their capability of adaptively improving spectral efficiency and reliability.
US 2009/0274140 discloses a wireless communication system employing a multi-channel MAC protocol based on a superframe concept, which includes
a multi-channel PHY superframe structure that logically organizes a plurality of channels including a superframe per channel with a control window of a fixed duration and a remaining part. One of the superframes is a logical channel defined as a meeting point channel used to synchronize with the system; a transmitter that transmits superframes according to the PHY superframe structure; and a receiver that listens for the PHY superframe structure on a predetermined set of channels of the plurality of channels, such that a device synchronizes/resynchronizes with the system by the receiver periodically listens to the meeting point channel. However, the proposed system requires a control channel for allowing nodes to coordinate which node can transmit and via which channel. This control channel substantially becomes a bottleneck of the system.
“TDMA scheduling design of multihop packet radio networks based on Latin Squares”, Ju et al, INFOCOM 1999, NY, U.S.A. discloses a multichannel topology-transparent algorithm for radio networks, based on Latin Squares with a guaranteed minimum throughput. The proposed algorithm has the flexibility to allow the growth of the network, i.e., the network can add more mobile nodes without recomputation of transmission schedules for existing nodes. However, in order to receive several channels within the same time slot, the proposed algorithm requires reception using several full-duplex receivers, which are costly.
“An Optimal Channel Access Protocol with Multiple Reception Capacity” (Chlamtac and Farago, IEEE Transactions on Computers, Vol. 43, No. 4, April 1994, pp 480-484) discloses A multiple channel access protocol has been for situations when the users of the system have multiple reception capacity and share several common channels. Under heavy homogeneous load, the protocol guarantees the maximum achievable throughput. The optimum throughput is achieved with minimum buffer size and with the smallest possible delay. It provides a collision free schedule of transmissions and can be applied to different systems, such as CDMA or FDMA packet radio networks. However, the system includes a fixed number of channels, regardless the number of active nodes, such that nodes fully occupy all the channels. For example, if there are 100 nodes and 50 channels, 50 nodes will transmit in each time slot and will not be able to receive each other. Therefore, the distribution of channels between nodes is not optimal. In addition, the proposed protocol is limited to unicast packets of fixed size.
It is therefore an object of the present invention, to improve the spectral efficiency and scalability of MANET systems.
It is another object of the present invention to provide an improved MANET system that is topology-aware and being capable of adapting its connectivity according to the number of “live” nodes.
It is a further object of the present invention to provide an improved MANET system that considers the presence of alien transceivers in its neighborhood, and being capable of adapting its connectivity to minimize interference.
It is yet another object of the present invention to provide an improved MANET system that is being capable of reducing latency (the amount of time it takes a packet of data to move across a network connection).
Other objects and advantages of the invention will become apparent as the description proceeds.